The present invention is generally directed to electronic data communications and is particularly directed to an improvement in a system for assigning access to time slots in a multiple-channel demand-assignment-multiple-access (DAMA) communication system.
DAMA communication systems are particularly useful in a network of user terminals that communicate with each other via a common communication link, such as a transponder in a communication satellite in Earth orbit. When a large number of user terminals share such a common communication link, it is necessary to assign different portions of the time and frequency spectrums for messages transmitted by the different user terminals to prevent interference between different messages that are transmitted simultaneously throughout the network. In a DAMA communication system, access to a plurality of different given user terminals is assigned in such a manner as to quickly and efficiently establish the communications linke for a large number of user terminals.
A prior art system for assigning to given user terminals in a multiple-user DAMA communication system access to time slots of time frames of a plurality of frequency channels within which to transmit messages identified in message-access requests from different given user terminals includes: means for storing a plurality of message-access requests from different given user terminals; means for processing the stored message-access requests to schedule the identified messages for transmission in accordance with information contained in the message-access requests identifying transmission parameters of the respective identified messages and in accordance with the number of available time slots by assigning access to different combinations of the time slots for respectively transmitting different messages identified by the processed message-access requests; and means for transmitting assignment information to the given user terminals identifying the time slots for which access has been assigned for the respective given user terminals, with the assignment information for different predetermined groups of user terminals being transmitted simultaneously to all of the different user terminals. The stored message-access requests may be reprocessed from time to time, such as every given number of time frames, in order to reassign access to different combinations of the time slots for respectively transmitting different messages. This allows frequent preemption of prior access assignments in favor of new messages of higher priority.
Only a segment of a typical message is transmitted during each time frame. Each segment of the message is compressed into a message burst which is transmitted during only a portion of the time slots of the time frame. The procedure for assigning the time slots has been to pack the message bursts of the different messages from the different user terminals into the time frame in such a manner as to minimize unassigned time slots, while adhering to equipment, protocol, connectivity, and priority constraints. To achieve this objective, a weight function is computed for each unscheduled burst. This weight function reflects the relative difficulty expected in finding time slots assignable to the unscheduled burst. The unscheduled bursts are then sorted by weight; and the processing means proceeds through the stored message-access requests. If no conflicts exist the processing means assigns time slots in the earliest available portion of the time frame to highest weighted burst. The user terminals are associated with different organizations, with some organizations being associated with more than one of the user terminals; and the message-access requests identify the organization associated with the user terminal and indicate a priority set by the organization for processing the message-access requests of the identified organization. To ensure that such priority is observed, the scheduling procedure includes a backtracking routine, which is performed whenever, after access to the time frame is assigned, a high priority message has not been scheduled and the aggregate duration of scheduled lower priority messages exceeds the duration of the high priority message. In the backtracking routine, the assignment of time slots for the lowest priority scheduled message is rescinded and the bursts are again weighted and sorted to effect the time slot assignments as described above. The backtracking routine is repeated whenever necessary to observe priority. The backtracking routine can on occasion delay the scheduling to such an extent that scheduling is not completed before it is time to transmit.